# -*- coding: utf-8 -*-            
# @Time : 2022/11/14 22:44
# @Author  : lining
# @FileName: 接雨水.py
"""
https://leetcode.cn/problems/trapping-rain-water/
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出：6
解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）
从宽度上进行计算，宽度默认为1
解题思路：
（1）单调递减栈
（2）栈空或者新的高度比栈顶高度低，入栈
（3）新的高度比栈顶高度高，出栈，计算面积。和前一根的左边高度进行比较，面积=前一根的宽度x（当前要入栈这跟和前一根的高度的较小值），
计算完成后，累加宽度，因为前一根已经出出栈了，和新的栈顶比较高度，如果还比栈顶高，新的宽度就是之前的累加的宽度加上栈顶的宽度
例子[4,3,2,1,3]
（1）4,3,2,1都入栈，3和栈顶1比较，比栈顶高，1出栈，并计算面积，面积=1这根柱子的宽度1x  （min(3,2)-原柱子高度）=1，宽度累加，0+1
（2）3再和新的栈顶2比较，比2高，把2这跟弹出栈顶，再和栈顶柱子进行比较高度，高度是3，再次计算面积，
面积=（2这根柱子的宽度+已经弹出栈顶的柱子的宽度1）x（min(3,2)-原柱子高度）=（1+1）x（3-2）=2
"""
class Solution:
    def trap(self, heights) -> int:
        # 存放面积
        areas = []
        # 存放单调递减栈,格式[[宽,高]],宽度为1
        stack = []
        for a,i in enumerate(heights):
            width = 0
            # 新的高度大于栈顶高度，计算面积
            while stack and i > stack[-1][1]:
                current = stack.pop()
                # 出栈一个数之后栈空，表示最左边没有东西挡着
                if not stack:
                    continue
                width = current[0]+width
                current_height = current[1]
                height = min(i, stack[-1][1])
                # 面积，宽：前一个矩形的宽度，高：左右两边比较小的高度
                area = width * (height-current_height)
                areas.append(area)
            # 新的高度小于栈顶高度，入栈
            stack.append([width+1, i])
        print(areas)


a = [0,1,0,2,1,0,1,3,2,1,2,1]
Solution().trap(a)
